package com.LeeCode;

import java.util.PriorityQueue;

/**
 * 矩阵中最大的三个菱形和
 */

public class Code1878 {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

    }

    private int[][] ds, as; // 主对角线方向前缀和，副对角线方向前缀和
    private int x, y, z; // 最大，严格次大，严格第三大

    public int[] getBiggestThree(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        ds = new int[n + 1][m + 1];
        as = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int v = grid[i][j];
                ds[i + 1][j + 1] = ds[i][j] + v; // ↘
                as[i + 1][j] = as[i][j + 1] + v; // ↙
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int v = grid[i][j];
                update(v);
                for (int k = 1; k <= i && i + k < n && k <= j && j + k < m; k++) {
                    int a = queryDiagonal(i - k, j, k); // 菱形右上
                    int b = queryAntiDiagonal(i - k + 1, j - 1, k - 1); // 菱形左上
                    int c = queryDiagonal(i, j - k, k); // 菱形左下
                    int d = queryAntiDiagonal(i, j + k, k + 1); // 菱形右下
                    update(a + b + c + d);
                }
            }
        }
        if (z == 0) return y == 0 ? new int[]{x} : new int[]{x, y};
        return new int[]{x, y, z};
    }

    private void update(int v) {
        if (v > x) {
            z = y;
            y = x;
            x = v;
        } else if (v < x && v > y) {
            z = y;
            y = v;
        } else if (v < y && v > z) {
            z = v;
        }
    }

    // 从 (x,y) 开始，向 ↘，连续的 k 个数的和
    private int queryDiagonal(int x, int y, int k) {
        return ds[x + k][y + k] - ds[x][y];
    }

    // 从 (x,y) 开始，向 ↙，连续的 k 个数的和
    private int queryAntiDiagonal(int x, int y, int k) {
        return as[x + k][y + 1 - k] - as[x][y + 1];
    }
}
